package com.zxy.javaarithmetic;

import com.zxy.javaarithmetic.bean.ListNode;
import com.zxy.javaarithmetic.bean.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic
 *  @文件名:   Test
 *  @创建者:   zhangxy
 *  @创建时间:  2019/1/10 16:44
 *  @描述：    TODO
 */
public class Test {

	public static void main(String[] args) {
		//		TreeNode root = new TreeNode(1);
		//		root.left = new TreeNode(2);
		//		root.right = new TreeNode(3);
		//
		//		root.left.left = new TreeNode(4);
		//		root.left.right = new TreeNode(5);
		//		root.left.right.left = new TreeNode(6);
		//
		//		root.right.right = new TreeNode(7);
		//		root.right.right.left = new TreeNode(8);
		//
		//		postOrder2(root);

		//		int[][] matrix = {{5},{7,8},{2,3,4},{4,9,6,1},{2,7,9,4,5}};
		//		System.out.println("-----"+ JKDynamicUtils.yanghuiTriangle(matrix));

		//		int[] data = {2,9,3,6,5,1,7};
		//		searchMaxLength(data,0,data.length,maxLength);
		//		System.out.println("------"+maxLength);

		//		int[] nums = {0,2,1,-3};
		//		System.out.println(threeSumClosest(nums,1));

//		TreeNode root = new TreeNode(1);
//		TreeNode p = new TreeNode(2);
//		TreeNode q = new TreeNode(3);
//
//		root.left = p;
//		root.right = q;
//
//		System.out.println(lowestCommonAncestor2(root, p, q).val+"  ");
//
//		int[] nums = {-4,-1,-1,0,1,2};
//		fourSum(nums,-1);

		Stack<String> stack = new Stack();
		stack.push("1");
		stack.push("2");
		stack.push("3");

		for (String s : stack) {
			System.out.print(s + " ");
		}

	}


	static class Pair<K, V> {
		private K k;
		private V v;

		public Pair(K k, V v) {
			this.k = k;
			this.v = v;
		}

		public K getKey() {
			return k;
		}

		public V getValue() {
			return v;
		}
	}

	//左右子节点都未遍历
	private static final int BOTH_NONE = 0;
	//已遍历左节点
	private static final int LEFT_DONE = 1;
	//左右节点都已遍历
	private static final int BOTH_DONE = 2;

	/**
	 * 利用栈实现
	 * 时间复杂度O(N)
	 * 空间复杂度O(N)
	 */
	private static TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
		TreeNode lcaTreeNode = null;
		TreeNode childNode = null;
		boolean one_node_find = false;

		Stack<Pair<TreeNode, Integer>> stack = new Stack<Pair<TreeNode, Integer>>();
		stack.push(new Pair<TreeNode, Integer>(root, BOTH_NONE));

		while (!stack.isEmpty()) {
			Pair<TreeNode, Integer> pair = stack.pop();
			TreeNode node = pair.getKey();
			int node_state = pair.getValue();

			if (node_state != BOTH_DONE) {
				if (node_state == BOTH_NONE) {
					if (node == p || node == q) {
						if (one_node_find) {
							return lcaTreeNode;
						}
						one_node_find = true;
						lcaTreeNode = node;
					}
					childNode = node.left;
					stack.push(new Pair<TreeNode, Integer>(node,LEFT_DONE));
				} else {
					childNode = node.right;
					stack.push(new Pair<TreeNode, Integer>(node,BOTH_DONE));
				}
				if(childNode != null){
					stack.push(new Pair<TreeNode, Integer>(childNode, BOTH_NONE));
				}

			} else {
				if (node == lcaTreeNode && one_node_find) {
					lcaTreeNode = stack.peek().getKey();
				}
			}
		}
		return null;
	}

	private static ListNode mergerSort2(ListNode head) {
		int n, count = 1;
		ListNode cur = head;
		ListNode left, right;
		ListNode dummy = new ListNode(0);
		ListNode dummyTail = dummy;
		for (n = 0; cur != null; cur = cur.next, n++) {}

		cur = head;
		while (count < n) {
			while (cur != null) {
				left = right = cur;
				for (int i = 1; i < count && right != null; i++) {
					right = right.next;
				}

				if (right != null) {
					ListNode temp = right.next;
					right.next = null;
					right = temp;
					for (int i = 1; i < count && temp != null; i++) {
						temp = temp.next;
					}
					if (temp == null || temp.next == null) {
						cur = null;
					} else {
						cur = temp.next;
						temp.next = null;
					}
				} else {
					cur = null;
				}

				ListNode mergeNode = merger(left, right);

				if (dummy.next == null) {
					dummy.next = mergeNode;
					dummyTail = mergeNode;
				} else {
					dummyTail.next = mergeNode;
				}
				while (dummyTail.next != null) {
					dummyTail = dummyTail.next;
				}
			}
			cur = dummy.next;
			dummy.next = null;
			count = count << 1;
		}
		return cur;
	}

	private static ListNode merger(ListNode lh, ListNode rh) {
		ListNode dummy = new ListNode(0);
		ListNode cur = dummy;

		while (lh != null && rh != null) {
			if (lh.val < rh.val) {
				cur.next = lh;
				lh = lh.next;
			} else {
				cur.next = rh;
				rh = rh.next;
			}
			cur = cur.next;
			cur.next = null;
		}

		if (lh != null) cur.next = lh;
		if (rh != null) cur.next = rh;

		return dummy.next;
	}

	public static int search(int[] nums, int target) {
		if (nums == null || nums.length == 0) return -1;

		int l = 0, r = nums.length - 1, mid;
		while (l <= r) {
			mid = (l + r) / 2;

			if (nums[mid] == target) {
				return mid;
			}
			if (nums[l] <= nums[mid]) {
				//左边是有序的
				if (target > nums[mid] || target < nums[l]) {
					l = mid + 1;
				} else {
					r = mid - 1;
				}

			} else {
				//右边是有序的
				if (target < nums[mid] || target > nums[r]) {
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}

		}

		return -1;
	}

	public static int maxSubArray(int[] nums) {
		//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
		int result = Integer.MIN_VALUE;
		int numsSize = nums.length;
		result = maxSubArrayHelper(nums, 0, numsSize - 1);
		return result;
	}

	public static int maxSubArrayHelper(int[] nums, int left, int right) {
		if (left == right) {
			return nums[left];
		}
		int mid = (left + right) / 2;
		int leftSum = maxSubArrayHelper(nums, left, mid);
		//注意这里应是mid + 1，否则left + 1 = right时，会无线循环
		int rightSum = maxSubArrayHelper(nums, mid + 1, right);
		int midSum = findMaxCrossingSubarray(nums, left, mid, right);
		int result = Math.max(leftSum, rightSum);
		result = Math.max(result, midSum);
		System.out.println("leftSum=" + leftSum + "  midSum=" + midSum + " rightSum=" + rightSum);
		return result;
	}

	public static int findMaxCrossingSubarray(int[] nums, int left, int mid, int right) {
		int leftSum = Integer.MIN_VALUE;
		int sum = 0;
		for (int i = mid; i >= left; i--) {
			sum += nums[i];
			leftSum = Math.max(leftSum, sum);
		}

		int rightSum = Integer.MIN_VALUE;
		sum = 0;
		//注意这里i = mid + 1，避免重复用到nums[i]
		for (int i = mid + 1; i <= right; i++) {
			sum += nums[i];
			rightSum = Math.max(rightSum, sum);
		}
		return (leftSum + rightSum);
	}

	public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
		if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
			int[] array = nums1 == null || nums1.length == 0 ? nums2 : nums1;
			int len = array.length;
			return len % 2 == 0 ? (array[(len - 1) / 2] + array[len / 2]) * 1.0f / 2 : array[len / 2];
		}

		//保证n >= m,就可以保证后面 j >= 0
		if (nums1.length > nums2.length) {
			int[] temp = nums1;
			nums1 = nums2;
			nums2 = temp;
		}
		int m = nums1.length, n = nums2.length, halfLen = (m + n + 1) / 2;
		// [iMin,iMax] 为i的搜索范围，i，j: 数组划分为两组，表示右侧数据的起点 i=0,表示没左侧数组，i=m,表示没右侧数组
		int iMin = 0, iMax = m, i, j;

		while (iMin <= iMax) {
			i = (iMin + iMax) / 2;
			j = halfLen - i;

			if (i > iMin && nums1[i - 1] > nums2[j]) {
				iMax = i - 1;
			} else if (i < iMax && nums2[j - 1] > nums1[i]) {
				iMin = i + 1;
			} else {
				int maxLeft;
				if (i == 0) {
					maxLeft = nums2[j - 1];
				} else if (j == 0) {
					maxLeft = nums1[i - 1];
				} else {
					maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
				}
				if ((m + n) % 2 == 1) return maxLeft;

				int minRight;
				if (i == m) {
					minRight = nums2[j];
				} else if (j == n) {
					minRight = nums1[i];
				} else {
					minRight = Math.min(nums1[i], nums2[j]);
				}
				return (maxLeft + minRight) * 1.0f / 2;
			}
		}
		return 0;
	}

	public static List<Integer> spiralOrder2(int[][] matrix) {
		List ans = new ArrayList();
		if (matrix.length == 0) return ans;
		int r1 = 0, r2 = matrix.length - 1;
		int c1 = 0, c2 = matrix[0].length - 1;
		while (r1 <= r2 && c1 <= c2) {
			for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
			for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
			if (r1 < r2 && c1 < c2) {
				for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
				for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
			}
			r1++;
			r2--;
			c1++;
			c2--;
		}
		return ans;
	}

	public static List<Integer> spiralOrder(int[][] matrix) {
		if (matrix == null || matrix.length == 0) return Collections.emptyList();

		int m = matrix.length;
		int n = matrix[0].length;
		List<Integer> resList = new ArrayList<>(m * n);
		int[][] flag = new int[m][n];
		int row = 0, column = 0;

		for (int i = 0; i < m * n; i++) {
			resList.add(matrix[row][column]);
			flag[row][column] = 1;

			if (column < n - 1 && flag[row][column + 1] == 0) {
				if (row > 0 && flag[row - 1][column] == 0) {
					row--;
				} else {
					column++;
				}
			} else if (column > 0 && flag[row][column - 1] == 0) {
				if (row < m - 1 && flag[row + 1][column] == 0) {
					row++;
				} else {
					column--;
				}
			} else if (row < m - 1 && flag[row + 1][column] == 0) {
				row++;
			} else if (row > 0 && flag[row - 1][column] == 0) {
				row--;
			}
			flag[row][column] = 1;
		}
		return resList;
	}

	public static List<List<Integer>> fourSum(int[] nums, int target) {
		int n = nums.length;
		if(n < 4) return Collections.EMPTY_LIST;

		int left,right,sum;
		List<List<Integer>> result = new ArrayList();

		//排序
		Arrays.sort(nums);

		for(int i = 0; i < n - 3; i++){
			//去重
			if(i > 0 && nums[i] == nums[i-1]){
				continue;
			}
			//剪枝
			if(nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target){
				break;
			}
			if(nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target){
				continue;
			}

			for(int j = i+1; j < n - 2; j++){
				//去重
				if(j > i+1 && nums[j] == nums[j-1]){
					continue;
				}
				//剪枝
				if(nums[i] + nums[j] + nums[j+1] + nums[j+2] > target){
					break;
				}
				if(nums[i] + nums[j] + nums[n-1] + nums[n-2] < target){
					continue;
				}

				left = j+1;
				right = n-1;

				while(left < right){
					sum = nums[i] + nums[j] + nums[left] + nums[right];
					if(sum == target){
						result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
						//去重
						while(++left < right && nums[left] == nums[left-1]){}
						while(--right > left && nums[right] == nums[right+1]){}
					}else if(sum > target){
						right--;
					}else{
						left++;
					}
				}
			}
		}
		return result;
	}

}
